package main.java.com.amanda.innovate;

import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.StdOut;

import java.util.Scanner;

/**
 * @author amanda
 * @Description get（）、put（）和 keys（）的非递归实现
 */

public class NonrecursiveBST<Key extends Comparable<Key>, Value> {

    private Node root;

    private class Node {
        private Key key;             // sorted by key
        private Value val;           // associated value
        private Node left, right;    // left and right subtrees
        public Node(Key key, Value val) {
            this.key = key;
            this.val = val;
        }
    }

    /***************************************************************************
     *  Insert key-value pair into symbol table (nonrecursive version).
     ***************************************************************************/
    public void put(Key key, Value val) {
        Node z = new Node(key, val);
        if (root == null) {
            root = z;
            return;
        }
        Node parent = null, x = root;
        while (x != null) {
            parent = x;
            int cmp = key.compareTo(x.key);
            if      (cmp < 0) x = x.left;
            else if (cmp > 0) x = x.right;
            else {
                x.val = val;
                return;
            }
        }
        int cmp = key.compareTo(parent.key);
        if (cmp < 0) parent.left  = z;
        else         parent.right = z;
    }

    /***************************************************************************
     *  Search BST for given key, nonrecursive version.
     ***************************************************************************/
    Value get(Key key) {
        Node x = root;
        while (x != null) {
            int cmp = key.compareTo(x.key);
            if      (cmp < 0) x = x.left;
            else if (cmp > 0) x = x.right;
            else return x.val;
        }
        return null;
    }

    /***************************************************************************
     *  Inorder traversal.
     ***************************************************************************/
    public Iterable<Key> keys() {
        Stack<Node> stack = new Stack<Node>();
        Queue<Key> queue = new Queue<Key>();
        Node x = root;
        while (x != null || !stack.isEmpty()) {
            if (x != null) {
                stack.push(x);
                x = x.left;
            }
            else {
                x = stack.pop();
                queue.enqueue(x.key);
                x = x.right;
            }
        }
        return queue;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        String[] ste = str.split(" ");
        int N = ste.length;

        NonrecursiveBST<String, Integer> st = new NonrecursiveBST<>();
        for (int i = 0; i < N; i++) {
            String key = ste[i];
            st.put(key, i);
        }
        for (String s : st.keys())
            StdOut.printf("%s\t",s);
        StdOut.println();
        for (String s : st.keys())
            StdOut.printf("%d\t",st.get(s));
    }
}
